package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

import java.util.Random;

/**
 * @author yww
 * @description 83. 删除排序链表中的重复元素
 * @since 2024/2/2 14:41
 */
public class DeleteDuplicates83 {
    // 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。
    // 返回 已排序的链表
    public ListNode deleteDuplicates(ListNode head) {
        int i = new Random().nextInt();
        if (i % 2 == 0) {
            del01(head);
            return head;
        } else {
            return del02(head);
        }
    }

    // 方法1：循环双指针
    private static void del01(ListNode cur) {
        if (cur == null || cur.next == null) {
            return;
        }

        // 指向待删除节点前驱
        ListNode p1 = cur;
        // 指向当前遍历节点
        ListNode p2;

        while ((p2 = p1.next) != null) {
            // 如果p1和p2节点值相等，保留p1，删除p2
            if (p1.val == p2.val) {
                p1.next = p2.next;
            } else {
                p1 = p1.next;
            }
        }
    }

    // 方法二：递归
    private static ListNode del02(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        // 如果当前节点和下一个节点值相同，递归返回下一个节点的递归处理，跳过当前节点
        if (cur.val == cur.next.val) {
            return del02(cur.next);
        } else {
            // 返回当前节点，并递归更新下个节点
            cur.next = del02(cur.next);
            return cur;
        }
    }
}
